package class09;

import java.util.HashSet;

/**
 * 贪心算法求解的标准过程
 * 1.分析业务
 * 2.根据业务逻辑找到不同的贪心策略
 * 3.对于能举出反例的策略直接跳过,不能举出反例的策略要证明有效性,
 * 这往往是特别困难的,要求数学能力高且不具有统一的技巧性
 *
 *
 * 贪心算法的解题套路
 * 1.实现一个不依靠贪心策略的解法X,可以用最暴力的尝试
 * 2.脑补出贪心策略A,贪心策略B,贪心策略C...
 * 3.用解法X和对数器,用实验的方式得知哪个贪心策略正确
 * 4.不要去纠结贪心策略的证明
 *
 */

/*
照亮一条路最少路灯问题, .位置为路可以放灯,需要照亮; x位置为墙不可以放灯也不需要被照亮;
*为灯,只能照亮放灯的位置及距离为1的位置

案例:
x..x......x..x.

放灯策略:
x.*x.*..*.x.*x*

 */
public class Code02_Light {

	//暴力法
	public static int minLight1(String road) {
		if (road == null || road.length() == 0) {
			return 0;
		}
		return process(road.toCharArray(), 0, new HashSet<>());
	}

	// str[index....]位置，自由选择放灯还是不放灯
	// str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
	// 要求选出能照亮所有.的方案，并且在这些有效的方案中，返回最少需要几个灯
	public static int process(char[] str, int index, HashSet<Integer> lights) {
		if (index == str.length) { // 结束的时候
			//验证是否都被照亮
			for (int i = 0; i < str.length; i++) {
				if (str[i] != 'X') {
					// 当前位置是点的话, 有距离1以内是否有灯
					if (!lights.contains(i - 1) 
							&& !lights.contains(i) 
							&& !lights.contains(i + 1)) {
						//无效解
						return Integer.MAX_VALUE;
					}
				}
			}
			return lights.size();
		} else { // str还没结束
			// i   X  .
			//先默认都不放灯
			int no = process(str, index + 1, lights);
			int yes = Integer.MAX_VALUE;
			if (str[index] == '.') {
				//再逐步尝试放灯
				lights.add(index);
				yes = process(str, index + 1, lights);
				//还原放灯的现场
				lights.remove(index);
			}
			return Math.min(no, yes);
		}
	}

	/**
	 * 贪心(在每一步最优)
	 * i位置是X, 直接到i+1的位置做决定
	 * i位置是.
	 * 		-> i+1位置是X, 那么i位置直接放灯
	 * 		-> i+1位置是.
	 * 			-> 	i+2位置是X, 那么.放i位置, 然后去i+3位置决定
	 * 			-> 	i+2位置是., 那么.放i+1位置, 然后去i+3位置决定
	 *
	 * @param road 路情况
	 * @return 最少灯数
	 */
	public static int minLight2(String road) {
		char[] str = road.toCharArray();
		int index = 0;
		int light = 0;
		while (index < str.length) {
			if (str[index] == 'X') {
				index++;
				//分情况时,保障了i位置不会被之前的位置所影响(潜规则),所以每次新到i可以只考虑后面
			} else { // i -> .
				//不管去哪个index, 至少放置了1盏灯
				light++;
				if (index + 1 == str.length) {
					break;
				} else {
					if (str[index + 1] == 'X') {
						index = index + 2;
					} else {
						index = index + 3;
					}
				}
			}
		}
		return light;
	}

	// for test
	public static String randomString(int len) {
		char[] res = new char[(int) (Math.random() * len) + 1];
		for (int i = 0; i < res.length; i++) {
			res[i] = Math.random() < 0.5 ? 'X' : '.';
		}
		return String.valueOf(res);
	}

	public static void main(String[] args) {
		int len = 20;
		int testTime = 100000;
		for (int i = 0; i < testTime; i++) {
			String test = randomString(len);
			int ans1 = minLight1(test);
			int ans2 = minLight2(test);
			if (ans1 != ans2) {
				System.out.println("oops!");
			}
		}
		System.out.println("finish!");
	}
}
